package org.aplombh.java.awcing.basic.graph.shortestPath.dijkstra;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
 * <p>
 * 请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
 * <p>
 * 输入格式
 * 第一行包含整数 n 和 m。
 * <p>
 * 接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
 * <p>
 * 输出格式
 * 输出一个整数，表示 1 号点到 n 号点的最短距离。
 * <p>
 * 如果路径不存在，则输出 −1。
 * <p>
 * 数据范围
 * 1≤n,m≤1.5×105,
 * 图中涉及边长均不小于 0，且不超过 10000。
 * 数据保证：如果最短路存在，则最短路的长度不超过 109。
 * <p>
 * 输入样例：
 * 3 3
 * 1 2 2
 * 2 3 1
 * 1 3 4
 * 输出样例：
 * 3
 */
public class Dijkstra_heap_850 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String s = reader.readLine();
        int n = Integer.parseInt(s.split(" ")[0]);
        int m = Integer.parseInt(s.split(" ")[1]);
        Dijkstra_heap dijkstra = new Dijkstra_heap(n);
        while (m-- != 0) {
            s = reader.readLine();
            int a = Integer.parseInt(s.split(" ")[0]);
            int b = Integer.parseInt(s.split(" ")[1]);
            int c = Integer.parseInt(s.split(" ")[2]);
            dijkstra.add(a, b, c);
        }
        System.out.println(dijkstra.dijkstra());
    }
}

class Dijkstra_heap {
    public static final int N = 150010;
    int[] h, w, e, ne; // 邻接表存储图 Store the graph
    int[] dist = new int[N]; // 到某点的最短距离 The distance to some point
    PriorityQueue<Pair> heap = new PriorityQueue<>(); // 优先队列
    boolean[] st = new boolean[N]; // 是否访问过  visited
    int n, idx;

    Dijkstra_heap(int n) {
        init(n);
    }

    void init(int n) {
        this.n = n;
        // 初始化 initialize
        h = new int[N];
        w = new int[N];
        e = new int[N];
        ne = new int[N];
        Arrays.fill(h, -1);
        Arrays.fill(dist, 1 << 30);
        dist[1] = 0;
    }

    void add(int a, int b, int c) {
        w[idx] = c;
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    public int dijkstra() {

        heap.add(new Pair(1, 0));

        while (heap.size() != 0) {
            Pair top = heap.remove();
            // 将最短路径取出 Fetching shortest path
            int ver = top.ver;
            int distance = top.distance;

            if (st[ver]) continue;
            for (int i = h[ver]; i != -1; i = ne[i]) {
                int j = e[i];
                // 如果该点修改了就将该点加入队列中
                if (dist[j] > distance + w[i]) {
                    dist[j] = distance + w[i];
                    heap.add(new Pair(j, dist[j]));
                }
            }
        }
        if (dist[n] == 1 << 30) return -1;
        return dist[n];
    }
}

class Pair implements Comparable<Pair> {
    int ver;
    int distance;

    public Pair(int ver, int distance) {
        this.ver = ver;
        this.distance = distance;
    }

    @Override
    public int compareTo(Pair o) {
        return this.distance - o.distance;
    }
}